package com.markus.code.剑指offer;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/31 13:32
 * todo: 机器人的运动范围
 */
public class MovingCount {
    public int movingCount(int m, int n, int k) {
        if (m < 0 || n < 0 || k < 0) {
            return 0;
        }
        boolean visited[][] = new boolean[m][n];
        int sum = process(m, n, 0, 0, k, visited);
        return sum;
    }

    private int process(int rows, int cols, int row, int col, int k, boolean[][] visited) {
        if (!isValid(rows, cols, row, col, k,visited)) {
            return 0;
        }
        visited[row][col] = true;
        return 1 + process(rows, cols, row + 1, col, k, visited) +
                process(rows, cols, row - 1, col, k, visited) +
                process(rows, cols, row, col + 1, k, visited) +
                process(rows, cols, row, col - 1, k, visited);
    }

    private boolean isValid(int rows, int cols, int row, int col, int k,boolean[][] visited) {
        if (row >= rows || row < 0 || col < 0 || col >= cols || (digitSum(row) + digitSum(col) > k) || visited[row][col]) {
            return false;
        }
        return true;
    }

    private int digitSum(int digit) {
        int sum = 0;
        while (digit > 0) {
            sum += digit % 10;
            digit /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        int m = 2;
        int n = 3;
        int k = 1;
        MovingCount demo = new MovingCount();
        System.out.println(demo.movingCount(m, n, k));
    }
}
